class Solution {
    int ret; // 结果：解的个数
    int _n; // 棋盘大小 n
    bool checkCol[10]; // checkCol[c] 表示第 c 列是否有皇后
    bool checkDig1[20]; // checkDig1[r - c + n] 表示从左上到右下的对角线（主对角线）
    bool checkDig2[20]; // checkDig2[r + c] 表示从右上到左下的对角线（副对角线）

public:
    int totalNQueens(int n) {
        _n = n;
        ret = 0; // 初始化解的数量为 0
        dfs(0); // 从第 0 行开始搜索
        return ret;
    }

private:
    void dfs(int row)
    {
        if (row == _n)
        {
            ret++; // 找到一个合法解，解数 +1
            return;
        }

        for (int col = 0; col < _n; ++col) // 枚举当前行的每一列
        {
            if (!checkCol[col] && !checkDig1[row - col + _n] && !checkDig2[row + col])
            {
                // 放置皇后（
                checkCol[col] = true;
                checkDig1[row - col + _n] = true;
                checkDig2[row + col] = true;

                dfs(row + 1);

                // 恢复现场（回溯）
                checkCol[col] = false;
                checkDig1[row - col + _n] = false;
                checkDig2[row + col] = false;
            }
        }
    }
};